package com.origin.niuke.dfs;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * NC221 集合的所有子集(二)
 * 算法：回溯
 *
 * @author yezh
 * @date 2022/11/24 21:38
 */
public class NC221 {

    ArrayList<ArrayList<Integer>> ans;

    public ArrayList<ArrayList<Integer>> subsets(int[] nums) {
        // write code here
        ans = new ArrayList<>();
        Arrays.sort(nums);
        dfs(0, nums, new ArrayList<>(), new boolean[nums.length]);
        return ans;
    }

    void dfs(int i, int[] nums, List<Integer> list, boolean[] used) {
        ans.add(new ArrayList<>(list));
        for (; i < nums.length; i++) {
            // 剪枝, 防止重复
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
            list.add(nums[i]);
            used[i] = true;
            dfs(i + 1, nums, list, used);
            used[i] = false;
            list.remove(list.size() - 1);
        }
    }

}
